package com.exam.practice;

/**
 * @Author: xin.wang  E-mail:xin.wang1@myt11.com
 * @CreateTime: 2022/1/18 16:48
 * @Description: 不相邻最大子序列和
 */
public class FifthPractice {
    /**
     * 给你一个数组，其长度为 n ，在其中选出一个子序列，子序列中任意两个数不能有相邻的下标（子序列可以为空）
     *
     * 示例1
     * 输入：3,[1,2,3]  返回值：4
     * 说明：有[],[1],[2],[3],[1,3] 4种选取方式其中[1,3]选取最优，答案为4
     * 示例2
     * 输入：4,[4,2,3,5]  返回值：9
     * 说明：其中[4,5]的选取方案是在满足不同时选取相邻位置的数的情况下是最优的答案
     * 示例3
     * 输入：1,[-1]  返回值：0
     * 说明：选择子序列为空最优
     * 示例4
     * 输入：5,[3,2,3,4,5]  返回值：11
     * 说明：其中选择[3,3,5]的方案是最优的答案
     *
     * @param args
     */
    public static void main(String[] args) {
        int[] array = {1,2,3};
        long result = subsequence(3, array);
        System.out.println(result);
    }


    public static long subsequence(int n, int[] array) {
        int[] bestArr = new int[n];
        bestArr[0] = array[0];
        if (n > 1) {
            bestArr[1] = Math.max(bestArr[0], array[1]);
        }
        for (int i = 2; i < n; i++) {
            bestArr[i] = Math.max(bestArr[i - 2] + array[i], bestArr[i - 1]);
        }
        if (bestArr[n - 1] < 0) { //选择子序列为空最优
            return 0;
        } else {
            return bestArr[n - 1];
        }
    }

}
